◀ Prev · Parts · Full · Next ▶

• Constructive martingales (Schnorr 1971): A martingale is a function d : { 0 , 1 } ∗ ∗ → → [ 0 , ∞ ∞ ) {\displaystyle d:\{0,1\}^{*}\to [0,\infty )} such that, for all finite strings w, d ( w ) = ( d ( w ⌢ ⌢ 0 ) + d ( w ⌢ ⌢ 1 ) ) / 2 {\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2} , where a ⌢ ⌢ b {\displaystyle a^{\smallfrown }b} is the concatenation of the strings a and b. This is called the "fairness condition": if a martingale is viewed as a betting strategy, then the above condition requires that the bettor plays against fair odds. A martingale d is said to succeed on a sequence S if lim sup n → → ∞ ∞ d ( S ↾ ↾ n ) = ∞ ∞ , {\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,} where S ↾ ↾ n {\displaystyle S\upharpoonright n} is the first n bits of S. A martingale d is constructive (also known as weakly computable, lower semi-computable) if there exists a computable function d ^ ^ : { 0 , 1 } ∗ ∗ × × N → → Q {\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }} such that, for all finite binary strings w

1. d ^ ^ ( w , t ) ≤ ≤ d ^ ^ ( w , t + 1 ) < d ( w ) , {\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),} for all positive integers t,

2. lim t → → ∞ ∞ d ^ ^ ( w , t ) = d ( w ) . {\displaystyle \lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).}

A sequence is Martin-Löf random if and only if no constructive martingale succeeds on it.

◀ Prev · Parts · Full · Next ▶